%\newpage
%\mbox{}
\chapter{基于可验证索引哈希树的高安全日志结构存储技术}\label{基于可验证索引哈希树的高安全日志结构存储技术}

针对云环境中数据存储的安全性问题，
% 加密安全存储I/O效率低下的问题，
本章提出一种高效的加密存储方案SwornDisk。SwornDisk基于LSM树（log-structured merge tree）结构和异地更新加密机制，实现了高效的数据加密和安全存储。SwornDisk通过异地更新加密机制避免了每次验证任何一个数据单元都需要对整个磁盘进行验证的困难，从而可以在不影响I/O性能的前提下有效保证数据的安全性。

\section{引言}
云安全是目前云计算研究的一个重点，
由于云被部署在基于网络互联的公共计算平台上，不同用户数据之间的物理界限被消除，使得
攻击者更容易实施在线的监听、窃取、篡改等攻击，传统的安全加密方法难以对针对云的新型攻击作出有效防御。
可信执行环境或Trusted  execution  environment（TEE）技术（如Intel SGX、AMD SEV和Ant HyperEnclave）
为公共云(不可信平台）上的可信计算问题提供了一个可行的解决方案。
TEE使得用户内存数据始终保持加密和强隔离状态，
从而确保了用户软件在云服务器内存中的数据安全。

然而在实际可信计算场景中，应用程序不仅需要在内存中安全执行，还需要在磁盘上安全存储，这要求数据的机密性、完整性和新鲜性。
目前，虽然这些TEE也提供了存储层的安全加密，但是这些方式是以牺牲I/O效率的代价来对用户的存储层提供安全保护的。
传统TEE文件加密系统如Intel SGX内置的PFS使用的是基于MHT结构的加密算法，
这种算法虽然具有很强的安全性，但是该算法不论读写每次都需要$O(logN)$的I/O开销，
而非加密文件系统是$O(1)$的，并且PFS所使用的本地更新方式为了保持写一致性，数据在写入前必须先全部写入日志，
这导致了二次写入的问题，导致I/O效率更低。此外，PFS并未对元数据进行加密，
这增加基于元数据分析的侧通道攻击的风险。

为了解决以上问题，本章提出了一种新的基于LSM架构的安全快速存储加密系统SwornDisk。
本章首先分析了PFS的本地更新模式在加密场景中低效的原因：本地更新模式下的存储系统为了保证其新鲜性，
必须使用安全性更强的MHT结构来进行加密，但也极大的增加了I/O开销。
为此，SwornDisk：1.使用基于LSM架构的异地更新模式有效解决了针对新鲜性的回滚攻击，并同时保证了系统的机密性、完整性、匿名性；
2.提出了新型存储加密结构MHBT，MHBT结合MHT和B树的特性，支持$O(1)$时间内同时完成验证与LSM树查找，
可以极大提升系统的I/O速度，在保证不低于PFS的$O(logN)$读复杂度下，提供$O(1)$复杂度的写机制；
3.提供了更偏向底层存储的块设备接口而不是文件系统接口，
用户可以根据需求自由的部署上层应用和下层设备，增加了TEE存储的应用范围和便利度。我们的实验结果表明：
SwornDisk在保证安全性的前提下，对于各种工作负载提供了不弱于PFS的I/O性能，以及大幅领先PFS的写性能。

\section{研究背景}

\subsection{安全模型}

\textbf{安全假设}：我们假设TEE硬件是可信的，它保护内存的机密性和完整性，以及其中软件的其他CPU状态。
此外，我们信任TEE边界内的所有软件组件，它们不会主动泄露加密数据，也不会被任何攻击者窃听。
我们还假设TEE中的软件能够进行远程认证，以安全地获取一些加密数据（如：SwornDisk创建加密存储时由用户生成的管理员密钥）。

\textbf{安全需求}：
\begin{itemize}
\item 机密性：数据的明文不能被非法获取，数据必须以密文的形式存储，无权限的用户无法获得密钥并解密出明文；
\item 完整性：数据的任意部分不能被非法篡改，即使遭到篡改，任何试图篡改的操作也都能应该被检测出来；
\item 新鲜性：数据的任意部分始终保持最新版本，数据不会被攻击者协同校验码一起回滚至历史合法版本来逃避完整性检测；
\item 匿名性：数据的信道应当保持非透明，数据在加解密以及硬件运行过程中不会流出有效的侧面信息被来被实施攻击。
\end{itemize}

\textbf{攻击者模型}：我们假设云环境中的攻击者具有比传统攻击者更很强的攻击手段，其具有以下特点：
\begin{itemize}
\item 有特权：有控制TEE外部任何软件或硬件的能力；
\item 在线攻击：可以在TEE中的任何生命周期发起攻击；
\item 主动攻击：具有主动窃听或篡改任何I/O请求的能力。
\end{itemize}

\textbf{回滚攻击}：
传统数据安全模型只注重数据的机密性与完整性，而通常不考虑新鲜性，这是因为传统
安全场景下的攻击者能力有限，并不在威胁模型的考虑中。
单纯实现数据的机密性与完整性可以简单的使用AES-GCM算法在$O(N)$时间复杂度完成数据明文加密，并生成明文的
MAC。但如果是对安全需求度更强的场景，如本章所述的云TEE，还需要保证数据的新鲜性，对于云存储中的块存储系统，
只对每个块执行AES-GCM加密不能保证安全性，因为在云TEE的威胁模型中，我们必须假设攻击者具有特权和在线、主动进行攻击的能力，
此时，攻击者虽然不能破坏由AES-GCM算法提供的机密性与完整性，但可使用回滚攻击来破坏数据的新鲜性。
回滚攻击的实施如图\ref{roll_back}所示，攻击者通过在线监听I/O的方式，
获得了数据块A的密文以及其MAC的历史版本v0，之后利用v0覆盖对当前时间点版本v1。显然用v0覆盖v1是一种
非法操作，但由于完整性校验只检查当前时间点A块的加密数据是否
与其MAC一致，v0版本虽然不是现在时间的合法版本v1，
但其上的加密数据与MAC却是过去生成出的合法版本，因此能够通过校验。
为了预防此类攻击，必须使用更强加密算法来对数据进行保护，Intel SGX除了在TEE中提供内存隔离
外，还集成了一套文件加密系统PFS来保证数据的机密性、完整性、新鲜性，
PFS常作为SGX默认的磁盘加密部件被广泛应用在TEE中。

\begin{figure}[htb]
	\centering
	\subfloat[]{\includegraphics[width=0.8\textwidth]{ppt-thesis/local_update.png}}\quad
	\subfloat[]{\includegraphics[width=0.8\textwidth]{ppt-thesis/outplace_update.png}}
	\caption{本地更新（a）模式下，A的物理位置固定，攻击者可收集A的历史数据来进行回滚攻击。异地更新（b）模式下，攻击者无法收集新写入数据A的历史版本来进行回滚攻击，因为A的物理地址是加密的。（A是数据的逻辑地址）}
	\label{roll_back}
\end{figure}

\subsection{PFS的主要问题}
PFS的加密基于MHT结构，在传统的加密MHT中，叶子节点用来保存数据块的密文，用AES-GCM加密，
MHT的中间节点称为哈希节点，保存其子节点的MAC和KEY（KEY由密钥生成算法随机生成），
并将其保存的子节点加密信息作为块数据，之后也使用AES-GCM加密。
这个过程是迭代的，也就是说叶子（密文）的KEY和MAC被保存在其父节点上，
其父节点的KEY与MAC被保存在其祖父节点上，一直到根。因此，要解密任意一个数据块，都要先获得该数据块的KEY和MAC（用于验证），
而数据块的KEY和MAC被保存在其父节点上，因此必须先得到其父节点的明文信息，
类似的，父节点的加密信息被保存在祖父节点上，所以还需要先解密祖父节点，
以此类推，重复这一过程直到根节点，再进行回溯，
时间复杂度为$O(log_{N})$，其中$N$是数据块的个数。
数据块的加密是类似的迭代过程，时间复杂度也为$O(log_{N})$。
MHT结构除为数据的机密性和完整性提供保护外，还可以提供新鲜性保护。在MHT中，攻击者试图对某个加密数据块进行了回滚，
必须连同其父节点一起回滚，因为数据块的加密信息（KEY和MAC）被保存在其父节点上，以此类推，攻击者必须要回滚从叶子到根的
一整条哈希链。但即使是这样，攻击也会被检测出来，因为当根节点被回滚后，其他数据块的验证无法通过。实际上，MHT中的每个
单独数据块的验证都可以认为是对整个加密存储总体的验证，所以唯一的攻击方法是回滚整个加密存储，
但这种代价过高的攻击手段在TEE中通常被认为是不实际的，也不在防御的范围之内。
相比PFS的高复杂度，非加密文件系统如EXT的I/O复杂度是$O(1)$的，PFS虽然保护了数据的安全性，却极大的牺牲了I/O性能。
此外，PFS为了保证写一致性，还存在二次写入问题，因为数据在被写入之前必须先被写入日志中，这导致写效率变得更差。

PFS低效的原因主要是因为TEE框架在存储层面采用的是传统的本地更新IO方式导致的。
由于目前云TEE环境不仅要保证传统安全需求中的机密性与完整性，还要保证其新鲜性，
而传统的本地更新方式让攻击者可以很容易地收集到相同物理位置的历史版本数据，
攻击者可以通过将加密数据回滚至历史合法版本来实施攻击。
为了保证新鲜性，每个块的完整性不能只通过其自身的MAC来验证，
所以PFS使用MHT结构的使得每次验证都关联到整个存储，
试图修改任何一个数据块的操作都会改变整个存储的MAC而被检测出来，
但这样做的话，每个I/O的验证过程是$O(logN)$的而不再是$O(1)$的。

\section{SwornDisk设计}

为了解决上述问题，我们提出了SwornDisk，一种基于LSM架构的异地更新安全加密存储系统。
SwornDisk使用LSM异地更新模式以及一种新型的存储加密数据结构MHBT来对LSM映射进行加密，在保证安全性的前提下，达到了$O(1)$的写理论复杂度，
并防止二次写入带来的额外开销，极大的加速了云TEE下存储写性能，在读性能方面，SwornDisk做到了不弱于PFS的$O(logN)$的理论复杂度，
并使用三级Cache来对其进行加速；其次，SwornDisk相比PFS提供了更偏向底层存储的块设备接口而不是文件系统接口，
用户可以根据需求在SwornDisk上层自由地部署文件系统如（EXT）或数据库等其他存储应用，而不需要对这些应用进行额外的加密，
这增加了TEE安全加密存储的应用范围和便利度。

\subsection{基本架构设计}
SwornDisk基于LSM架构所设计，在基本的LSM架构中，数据块并不是本地更新的，而是每次选择一个新的空闲块位置进行更新，
由于其物理地址会发生改变，因此存储系统需要能根据其逻辑地址找到其最新的物理地址。
LSM架构中的LSM树维护了所有数据块逻辑地址到物理地址的映射，
每次读取前，先进入LSM树中根据逻辑地址到物理地址的映射，查找到其物理地址，再进行读入；
对于写，如上所述，会选择一个新的空闲块写入，再更新其LSM树中的映射，原先物理地址的数据块将被废弃，并变成一个新的空闲块。
为了提高LSM树查找映射的速度，LSM树被分为内存的C0+磁盘的C1两部分组成，查找映射会先进入C0查找，未找到再进入C1。
由于内存相比磁盘空间有限，当C0容量变满时，要将C0迁移到C1上，并作为一个新的SST进行持久化。LSM-C1由许多SST组成，
由于SST是按照写入的先后顺序持久化的，如果对于LBA相同的映射，最后加入C1的映射保存了最新的PBA，因此C1的查找是由后往前进行的。
LSM树有多种实现方式，在SwornDisk的设计中，C0使用的是Hash\_map，
可以在$O(1)$理论复杂度内完成查找，而C1使用的是MHBT结构，
MHBT除了提供查找功能还对C1进行了快速加密，将会在后文中详细介绍。

SwornDisk的基本架构如图\ref{en_art}所示：蓝色方块表示磁盘上的各个区域，
分别维护了加密数据、LSM-C1、日志、元数据，并在括号中展示了其加密方法；绿色方块表示内存中分别维护的
包括数据Cache、LSM-C0、LSM-C1 Cache三种数据结构，由于TEE提供了基于内存隔离的内存安全保护，我们可以认为内存中的数据都是安全的，
因此不需要加密。蓝色方块与绿色方块之间的箭头表示磁盘与内存之间的逻辑交互关系，会在后面详细介绍。

\noindent
\textbf{磁盘布局}：
磁盘布局分为四个区域，分别是：元数据区、数据区、映射区、日志区。
\begin{itemize}
\item
元数据区：存放元数据信息，用于管理其他各区的资源信息，包括各个区的物理地址起始偏移、容量，以及一个用于标记所有块是否有效的bitmap。

\item
数据区：存放加密数据块的区域。

\item
映射区：存放LSM-C1映射的区域，用MHBT进行加密。

\item
日志区：存放日志，用于写一致性的恢复。
\end{itemize}

所有四个区域的数据都是加密的，这可以避免泄露任何有效信息来使攻击者进行侧通道攻击。不同区域的加密方法有所区别，
元数据区采用本地更新方式并直接用AES-GCM加密，其他区域采用的是异地更新方式，元数据不能采用异地更新，因为
异地更新本身就需要元数据来维护，这会导致一个无穷迭代的过程。数据区的每个块使用随机密钥进行AES-GCM加密，其KEY和MAC
连同其物理地址一起被保存在映射区中，映射区由MHBT进行加密，日志区负责存放日志，由于日志不会被二次访问的特殊性，我们
使用链式哈希算法来进行快速加密。

\noindent
\textbf{块设备接口}：与PFS提供的针对文件读写的接口不同，
SwornDisk基于Linux设备映射机制（Device Mapper）实现了一个安全加密的逻辑块设备，
给上层如文件系统、数据库等应用提供了针对逻辑地址LBA块的写入（write）、读取（read）、刷新（flush）接口，
上层应用通过逻辑地址LBA来对SwornDisk块设备进行操作。

\begin{itemize}
\item write(LBA, nblocks, buf)：将buf写入LBA所对应的块中，nblocks表示一次写入块的个数;
\item read(LBA, nblocks, buf)：读取LBA位置开始的nblocks个块，并将其存入buf中;
\item flush()：清空写缓存区，执行后保证所有的数据都完成落盘。
\end{itemize}

SwornDisk下层是物理地址PBA的接口，但这些PBA块接口的实现并不在SwornDisk中，而是由其他的块设备所实现
这些下层块设备可以是磁盘也可以是其他的逻辑块设备（比如前一章的DM-cache），SwornDisk通过设备映射机制将I/O转发到下层的
块设备上。这种基于块设备的设计可以为用户提供极大的便利，用户可以自由选择部署SwornDisk的上层或下层。

\noindent
\textbf{异地更新机制}
SwornDisk基于LSM存储架构提高传统加密存储的I/O性能，同时额外实现了一整套加密措施来保证其安全性。
SwornDisk对于每个针对逻辑地址新写入数据块，先在内存中生成一个新的随机密钥KEY，
然后用该KEY对数据明文使用AES-GCM算法进行加密得到密文以及MAC，后将密文以追加写的方式写入数据区并返回其物理地址。
为了能够通过LBA找到其PBA并解密，我们还要维护一个支持查找LBA到PBA映射的数据结构——二级LSM树，
LSM树是一个映射集合，其中的映射格式为：<LBA,(PBA,MAC,KEY)>。
数据块在读的时候先根据其LBA在LSM树中的映射找到其PBA、MAC、KEY，PBA用于定位
之前写入的物理地址，KEY和MAC用于解密物理地址上的密文来得到明文。

\noindent
\textbf{管理员密钥}：管理员密钥是块设备初始格式化时的唯一初始密钥，
由用户直接进行保管，用来加密一些元数据信息。除此之外的
所有其他密钥都是由加密算法级别的随机密钥生成器所随机生成，
用户不需要知道这些其他密钥的具体值，因为这些密钥只用来传递保护关系。

\noindent
\textbf{安全性分析}：
相比本地更新，异地更新方式可以有效地避免回滚攻击，因为在异地更新中相同物理地址的历史数据，并不是相同逻辑地址的历史数据，攻击者
如果简单地利用同一物理地址的历史版本覆盖当前版本是无效的，因为在异地更新中同一物理地址的只存在一个历史版本（如果先不考虑回收的话），
即使覆盖也并不会对磁盘作出任何改变。此时，攻击者若想达成攻击，只有先找到历史数据的最新物理地址，
但最新物理地址是由其逻辑地址在LSM中的映射所决定的，
并且这些映射由MHBT所保护，阻止了攻击者试图寻找新物理地址的行为。
SwornDisk通过对所有数据的进行加密提供了机密性、完整性以及一定程度上的匿名性保护（完全杜绝针对匿名性的侧通道攻击是被认为是不可能的，
但对包括元数据在内的所有磁盘数据进行加密可以阻止攻击者获得元数据信息来发起攻击）。
此外，通过异地更新方式，数据块的安全由LSM树所保护，而LSM树又由MHBT提供加密，因此可以有效防止回滚攻击，保证系统的新鲜性。
综上所述，SwornDisk的设计在云TEE下是安全的。

\begin{figure}[t]
  \includegraphics[width=0.8\linewidth]{ppt-thesis/en_art.pdf}
  \centering
  \caption{SwornDisk架构图}
  %\vspace{-3mm}
  \label{en_art}
\end{figure}


\subsection{I/O}

在SwornDisk中，I/O过程除了数据读写外，还涉及到加解密，其读过程如图\ref{en_read}所示。当接收到一个新的读请求时，SwornDisk首先根据其LBA查找
数据Cache，若命中则直接从内存中返回其明文，若未命中则进入LSM-C0中查找其LBA到PBA的映射，以及该数据块的KEY和MAC；若在LSM-C0中找到该映射，则直接
返回其PBA、KEY、MAC，否则将进入LSM-C1进行查找；LSM-C1将根据先后顺序遍历其上所有的SST（由MHBT实现），并且在每个MHBT中存在
一条查找路径，LSM-C1 Cache缓存了部分路径上的节点，因此，如果可以在LSM-C1 Cache中查找到这些节点，则直接跳到下一个节点上，否则将进入磁盘
查找当前节点；通过在LSM-C0或LSM-C1上的映射所返回的PBA、MAC、KEY，找到PBA所在的数据块，并对其用KEY进行解密、MAC进行验证，返回数据块的明文。


\begin{figure}[t]
  \includegraphics[width=0.8\linewidth]{ppt-thesis/en_read.pdf}
  \centering
  \caption{SwornDisk读过程
  }
  %\vspace{-3mm}
  \label{en_read}
\end{figure}

SwornDisk的写过程如图\ref{en_write}所示。当接收到一个新的写请求时，SwornDisk首先找到一个新的空闲块，用AES-GCM加密后直接写入，并标记检查点0，
并将PBA、KEY、MAC输入内存。
之后将其PBA、KEY、MAC与LBA组成一组新映射<LBA,(PBA, KEY, MAC)>同步写入LSM-C0和日志中，这一过程是同步的，
日志写成功后会标记一个检查点1表示成功写入成功。
之后更新元数据区的bitmap，并标记检查点2，后返回写成功。之后，判断LSM-C0容量是否变满，若C0容量已满则触发C0到C1的迁移，迁移完成后标记一个检查点3，返回迁移成功；之后清空日志，完成后标记检查点4。

\begin{figure}[t]
  \includegraphics[width=0.8\linewidth]{ppt-thesis/en_write.pdf}
  \centering
  \caption{SwornDisk写过程
  }
  %\vspace{-3mm}
  \label{en_write}
\end{figure}

\noindent
\textbf{写一致性}：
当系统发生崩溃时，由于日志保存了之前所有C0映射的记录，我们可以通过日志来恢复C0。
我们根据系统崩溃后检查点的状态分别进行处理。

\begin{itemize}
\item 0未标记：写数据时崩溃，此时没有迁移发生也未更新bitmap，该块会被视为一个空闲块，并视为上次写入失败，重启后通过日志恢复C0。
\item 0标记，1未标记：写日志时崩溃，删除最后一个写入的日志，也视为上次写入失败，重启后通过日志恢复C0。
\item 1标记，2未标记：更新bitmap时崩溃，重启后根据最后一个日志情况恢复bitmap，并恢复C0。
\item 1标记，3未标记：C0到C1迁移时崩溃，由于写C0与写日志是同步的，迁移一定发生在检查点1被标记之后，视为迁移失败，重启后重新迁移C0。
\item 3标记，4未标记：清空日志时崩溃，重启后重新清空日志。
\end{itemize}

综上，所有可能崩溃的时间点都不会发生不一致的情况，因此存储的写一致性可以得到保证。

\subsection{SST加密数据结构MHBT}

未加密的SST通常直接以LBA为序，转化为有序序列的形式保存在映射区内。在SST中查找LBA的过程，可以用二分查找来完成，其复杂度是$O(logN)$的，
这里$N$是序列长度。
因为MHT结构已具备足够的安全性，所以SST也可以直接使用MHT进行加密，只要将SST映射的有序序列当做是MHT的数据节点即可，并根据数据节点生成整棵MHT，
但这样做会导致查找的复杂度变为$O(log_{N}^{2})$的。具体分析如下：在SST查找一个具体的LBA是一个二分查找的过程，
二分查找的每次迭代都需要先解密出当前二分区间中点的LBA，然后才可以判断下次查找的是左区间或右区间，而读取MHT中任何一个数据节点的代价是$O(logN)$的，
由于二分查找总共有$O(logN)$次迭代，因此总复杂度为$O(log_{N}^{2})$。

这个复杂度比PFS的读复杂度更高，会大大增加读I/O开销。为此，我们设计了一种新型的加密数据结构MHBT（Merkle Hash B-Tree），MHBT利用SST序列的有序性，巧妙的将查找与解密验证融合在了一起，转化为单次MHT路径查找过程，其读复杂度是$O(logN)$。

MHBT结构在是MHT结构中加入B树的索引信息，使其具有B树快速二分查找的性质。MHBT继承MHT的特性，其叶子节点为映射节点用于保存数据区加密数据块的<LBA,(PBA,KEY,MAC)>，非叶子为哈希节点（用于保存加密信息，即KEY和MAC），非叶子节点除了保存其所有儿子节点（块）的<KEY,MAC>外，还增加了的<IDX, POS>域，其中IDX用于B树的二分查找，POS用于定位该节点在映射域中的物理位置（偏移量），因此其儿子的完整信息为<IDX,(POS,KEY,MAC)>，这类似于映射节点中的加密数据块的映射，我们也将其称为映射，其中IDX、POS与LBA、PBA一样为64字节。因此MHBT中的每个节点，不论映射节点（叶子）或哈希节点（中间节点）都有一个映射被保存在其父亲节点上。类似于B树，映射中IDX域的值为该节点所有儿子的IDX的最小值，图\ref{mhbt}展示了一个具体的MHBT例子。

\begin{figure}[t]
  \includegraphics[width=0.8\linewidth]{ppt-thesis/mhbt.png}
  \centering
  \caption{MHBT结构例子，每个方块都是一个存储块。黄色方块为加密数据块，其数字表示其逻辑地址LBA，并存储在数据区；淡蓝色块为映射节点，其数字表示其保存的加密数据块的LBA；蓝色方块为Hash节点，数字表示其IDX域；橘黄色方块是根节点，并且存储在元数据区。此图中每个数据块只保存了2个映射。
  }
  %\vspace{-3mm}
  \label{mhbt}
\end{figure}

MHBT根节点虽然没有父亲，但也有一条映射，该映射被保存在映射域的元数据中，称为M节点，M节点不再有自己的映射，并且M节点使用管理员密钥进行加密。MHBT的每个节点都是一个块，保存其所有儿子的映射，为了节省空间，我们尽可能地使用每个块的空间，所以每个块上面保存了$k=$Block\_size $/$ Mapping\_size个映射，其中Block\_size是块大小，Mapping\_size是每条映射的大小，为了方便，我们把MHBT的度（树的分叉数）也设置为此值（具体实现中Block\_size为4096字节，Mapping\_size为384字节，因此共可以保存10个映射，MHBT的度也是10）。

\noindent
\textbf{MHBT查找算法}
在MHBT中查找LBA及其映射的过程是遍历一条MHBT路径的过程，该路径的起始点是M节点，终点是目标LBA所在的叶子（映射节点），因此共需遍历$O(logN)$个节点，
每个节点之上的开销为$O(1)$常数级别，因此总复杂度为$O(logN)$。其具体查找过程可以表述为算法\ref{alg:mhbt_read}
(虽然在每个节点上要依次比较LBA和其儿子的IDX，但该过程在内存中执行，而且在实现中被固定为常数10，因此不计算在复杂度中),图\ref{mhbt_read}展示了
算法在图\ref{mhbt}上具体执行的例子。

\begin{algorithm}[t]
\caption{MHBT查找算法}
\label{alg:mhbt_read}
\begin{algorithmic}
\STATE 初始化$x=$根节点
\STATE 用管理员密钥解密M节点得到根节点$x$的KEY、MAC、POS
\WHILE {$x \neq$ 叶子}
\STATE 磁盘I/O：读取POS$_{x}$所指向的MHBT节点块$b$
\STATE 用KEY$_{x}$解密和MAC$_{x}$验证块$b$，得到$b$的明文：其所有儿子的映射
\FOR {$i=x$的儿子}
\IF {IDX$_{i}$ > LBA}
\STATE break
\ENDIF
\ENDFOR
\IF {$i = 0$}
\RETURN 未找到LBA //超出B树范围，说明不在该SST中
\ELSE
\STATE $x = i - 1$
\ENDIF
\ENDWHILE
\STATE /**** 找到映射节点（叶子） ****/
\STATE 磁盘I/O：读取PBA$_{x}$所指向的数据块$b$ //磁盘I/O
\STATE 用KEY$_{x}$解密和MAC$_{x}$验证块$b$，得到$b$的明文：LBA对应的数据块
\RETURN $b$的明文
%\vspace{-3mm}
\end{algorithmic}
\end{algorithm}

\noindent
\textbf{MHBT后序写入算法}：
未加密的C0有序序列在迁移到C1时可以很简单的实现，
只需要指迁移时按照内存中LSM-C0每条映射的LBA顺序以FIFO的方式将映射
写入磁盘即可，并且每写入一个映射就可以释放掉这部分内存，从而保持内存占用较小。。
而对于MHT或MHBT，传统方式是在内存中先构造出其序列化数据，再一次写入磁盘，
这需要额外申请一片等于LSM-C0的内存空间，而且这种方法无法处理SST合并的情况，
由于SST合并使用的是归并排序算法，需要事先将所有LSM-C1中的SST读入内存，如果这些SST的总大小超过内存容量，则无法执行合并。

为此，我们设计MHBT后序写入算法，利用其树的后序遍历，我们可以在只额外在内存中申请$logN$个块空间
的条件下完成迁移，这些申请的块空间用来保存MHBT每一层未写入磁盘的新块。我们仍然是以C0映射序列的LBA顺序，
依次写入磁盘的，C0的映射会先写入内存中的MHBT的叶子块，
之后会判断该叶子是否写满，如果写满，会将该叶子写入磁盘，并在内存中生成一个该叶子的父亲块。
当父亲块写满时，会将父亲块写入磁盘并生成一个祖父块，这一过程是迭代的，一直到根。具体的算法可表述为\ref{alg:mhbt_write}，
其中$q[k]$表示MHBT第$k$层在内存中未写入的块。
图\ref{mhbt_write}展示了一个C0迁移的例子，图\ref{mhbt_layout}展示了该例子MHBT在磁盘上的具体布局。

\begin{algorithm}[t]
\caption{MHBT后序写入算法}
\label{alg:mhbt_write}
\begin{algorithmic}
\STATE sort(LSM-C0映射)
\STATE offset$ = 0$;
\FOR {i=LSM-C0每个映射}
    \STATE $k = 0$
    \REPEAT
    \STATE $q[k]$.push\_back(i)
    \IF {$q[k]$已满}
        \STATE 磁盘I/O：$q[k]$写入offset
        \STATE q[k].POS=offset
        \IF {k=0}
            \STATE q[k].IDX=q[k][0].LBA
        \ELSE
            \STATE q[k].IDX=q[k][0].IDX
        \ENDIF
        \STATE $q[k]$.clear()
        \STATE $q[k + 1]$.push\_back
        \STATE $k += 1$
    \ELSE
        \STATE break
    \ENDIF
    \UNTIL $k > logN$
\ENDFOR
\end{algorithmic}
\end{algorithm}


\begin{figure}[t]
  \includegraphics[width=0.8\linewidth]{ppt-thesis/mhbt_read.png}
  \centering
  \caption{MHBT查找过程的例子，红色箭头表示查找的方向。
  }
  %\vspace{-3mm}
  \label{mhbt_read}
\end{figure}

\begin{figure}[t]
  \includegraphics[width=0.8\linewidth]{ppt-thesis/mhbt_write.png}
  \centering
  \caption{MHBT从C0迁移至C1的例子，圆圈中的数字表示该数据块持久至磁盘的顺序。
  }
  %\vspace{-3mm}
  \label{mhbt_write}
\end{figure}

\begin{figure}[t]
  \includegraphics[width=0.8\linewidth]{ppt-thesis/mhbt_layout.png}
  \centering
  \caption{图\ref{mhbt_write}例子中实际磁盘布局。
  }
  %\vspace{-3mm}
  \label{mhbt_layout}
\end{figure}


\subsection{链式哈希加密日志}:
由于日志的每个块至多在崩溃恢复时被读取一次，并且是在恢复中一次性全部读入，我们可以用复杂度更低,链式哈希结构对其加密。

\subsection{缓存}
我们的方案使用内存作为磁盘的cache来进行优化，我们cache共分为三级，第一级是对逻辑地址所映射的数据直接进行cache，如果命中，这种情况不需要任何磁盘读；第二级是LSM-C0 cache，这一级cache虽然不能直接提供数据，但提供了数据的逻辑地址到的物理地址的映射，如果命中，只需要1次读磁盘；第三级是LSM-C1 cache，如果前两级cache都不能命中，则需要到SSTable中查找其物理地址，第三级cache保存了最近访问的SSTable中的部分block，如果命中，可以大幅减少二分查找时的读磁盘的次数。与pfs相比，虽然pfs也会使用cache，但是由于pfs是本地更新，只能将数据进行cache，这等同于我们的第一级cache，由于磁盘上的数据量要比内存容量大得多，这种cache能保存的数据量十分有限，在随机读时作用很小，而我们的第二级与第三级cache保存的不是数据而是索引，其体量比数据要小得多，因此可以cache住更多的信息，从而大幅提升读速度。

\section{实验}
我们的测试机运行 CentOS 7操作系统，具有36核Intel gold 6240 2.60GHz CPU和64GB内存，以及一个 NVMe 400GB SSD。我们的测试程序使用fio基准测试工具执行包括顺序读入(rw-read)、顺序写入(rw-write)、随机读入(rw-randread)和随机写入（rw-randwrite）对不同类型的存储系统基于不同的block-size（每次IO的数据大小，注意fio block-size与存储系统内置的块大小的区别，后者是存储系统的内置参数，表示存储系统分块的大小）进行IO带宽测试，测试的存储系统包括非加密的Ext4文件系统，以及加密的存储系统分别包括：SwornDisk、Intel-PFS(fast-memory)、Rust-PFS、加密Ext4。Intel-PFS(fast-memory)是我们基于标准开源Intel-PFS代码进行了访存优化后的测试系统，我们主要通过对Intel-PFS内置的内存分配函数进行了改进，使其速度得到了有效改善，而原始Intel-PFS的写速度仅为改进后的0.2倍左右，我们这样做是出于比较的公平性。Rust-PFS是我们使用Rust安全语言实现的另一套与Intel-PFS逻辑相同的加密文件系统（Intel-PFS使用C++语言实现）。加密Ext4文件系统基于Ext4对每个文件数据块增加了AES-GCM加密，但其本身仍不具备本章所述的新鲜性、匿名性保护，没有实际应用价值，仅仅是用来比对AES-GCM加密算法对IO的负担，以及帮助我们衡量加密存储的性能上限，由于加密Ext4仅仅是Ext4增加了基本的数据加密功能，所以其性能指标可以一定程度上看做是加密存储系统的性能上限。同样为了公平起见，实验中的SwornDisk在上层部署了Ext4文件系统，以避免因文件系统本身的开销造成测试结果不准确。

\subsection{顺序IO测试}
我们首先对各个存储系统的顺序读带宽进行比较，如图\ref{fig:swsr}所示，未加密的Ext4文件系统的带宽达到了最高吞吐量，
仅接着是加密Ext4。SwornDisk、Intel-PFS、Rust-PFS的顺序读带宽相差不大，并且只略微落后于加密Ext4。虽然SwornDisk与两种PFS
的读IO的理论复杂度为$O(logN)$，但它们都使用了缓存对读进行优化，特别是顺序读具有较强的缓存局部性，因此其吞吐量并不会明显落后于理论复杂度$O(1)$的
加密Ext4，SwornDisk的顺序读也不会成为系统的瓶颈。此外，在顺序读测试中，block-size大小并不会大幅度影响IO的带宽性能，
因为各类存储系统都采用了数据预读机制，这点在之后的顺序写上也是相似的。

我们接着比较各个存储系统的顺序写带宽，如图\ref{fig:swsw}所示，此时未加密Ext4依然保持最高吞吐，加密Ext4仅略微落后，
接着SwornDisk略微落后加密Ext4，约为580MB/s，而两种PFS系统的性能相比顺序读而言出现了极大的下滑，仅约为100MB/s，
这是由于SwornDisk与Ext4的写复杂均为$O(1)$，而两种
PFS的写复杂度是$O(logN)$的，几种存储系统的复杂度上就有者很大差距。
由此可见，SwornDisk在顺序写性能上相比传统的PFS有着巨大提升，大约加速5.8倍。

\begin{figure}[t]
	\includegraphics[width=0.8\linewidth]{figs/sworndisk/swsr.png}
	\centering
	\caption{MapperX($\beta = 0.01,0.001,0.0001$)与DM-cache(\texttt{normal})在平均延迟上的对比。
	}
	%\vspace{-3mm}
	\label{fig:swsr}
\end{figure}

\begin{figure}[t]
	\includegraphics[width=0.8\linewidth]{figs/sworndisk/swsw.png}
	\centering
	\caption{MapperX($\beta = 0.01,0.001,0.0001$)与DM-cache(\texttt{normal})在尾延迟上的对比。
	}
	%\vspace{-3mm}
	\label{fig:swsw}
\end{figure}

\subsection{随机IO测试}
我们测试各个存储系统在随机IO上的性能，我们首先比较它们的随机读带宽，如图\ref{fig:swrr}所示，与顺序读不同的是，随机读带宽性能将随着
block-size大小而显著提升，这一方面是因为在随机IO中，小block-size的数据预读的效果将变差，另一方面也因为磁盘对于顺序IO的速度要高于
随机IO，而大block-size的随机IO仍然能保持单个IO在block-size范围内的顺序性。在随机读测试中，未加密Ext依然保持最高的吞吐量，
紧随其后的是加密Ext4，而SwornDisk、Intel-PFS、Rust-PFS落后于加密Ext4，且相互之间差距很小。

我们接着比较各个存储系统的随机写带宽，如图\ref{fig:swrw}所示，除了当block-size=1024KB时，SwornDisk略微落后未加密Ext4的性能外，
其他情况下，SwornDisk在随机写带宽上明显优于其他各类存储系统，并稳定在580MB/s左右，与其顺序写带宽接近。这主要得益于SwornDisk的LSM架构
可以将上层的逻辑随机写转为底层的物理顺序追加写，其复杂度为$O(1)$，并能以利用磁盘的高顺序写性能进行加速，
而PFS的复杂度为$O(logN)$，并且不能利用磁盘的顺序写机制。
相比之下，两类PFS系统在block-size=4KB至1024Kb的设置下，
仅达到了约5MB至100MB的带宽性能，SwornDisk相比PFS获得了约5.8至116倍的性能提升，大幅提高了加密存储系统特别是面向小型写IO的随机写性能。

\begin{figure}[t]
	\includegraphics[width=0.8\linewidth]{figs/sworndisk/swrr.png}
	\centering
	\caption{MapperX($\beta = 0.01,0.001,0.0001$)与DM-cache(\texttt{normal})在平均延迟上的对比。
	}
	%\vspace{-3mm}
	\label{fig:swrr}
\end{figure}

\begin{figure}[t]
	\includegraphics[width=0.8\linewidth]{figs/sworndisk/swrw.png}
	\centering
	\caption{MapperX($\beta = 0.01,0.001,0.0001$)与DM-cache(\texttt{normal})在尾延迟上的对比。
	}
	%\vspace{-3mm}
	\label{fig:swrw}
\end{figure}


\section{本章小结}

本章节研究了云环境中加密存储的安全性问题，本章提出了一种新的基于LSM架构的安全快速存储加密系统SwornDisk。
SwornDisk相比传统的PFS加密系统具有三点优势：首先，SwornDisk使用基于LSM架构的异地更新模式有效解决了针对新鲜性的回滚攻击，
并同时保证了系统的机密性、完整性、匿名性；其次SwornDisk使用新型存储加密结构MHBT，支持$O(1)$时间内同时完成验证与LSM树查找，
大幅提升加密系统的I/O速度，在保证不低于PFS的$O(logN)$读复杂度下，提供$O(1)$复杂度的写速度；
第三，SwornDisk提供了更偏向底层存储的块设备接口而不是文件系统接口，
用户可以根据需求自由的部署上层应用和下层设备，相比PFS而言增加了TEE存储的应用范围和自由度。我们的实验结果表明：
SwornDisk在保证安全性的前提下，获得了大幅领先PFS写性能。
